package leetcode.code0850;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

import leetcode.helper.HelpDebug;

public class Solution extends S850 {

	private class Node {
		private int LeftRange;
		private int RightRange;
		private int Mid;
		private long segmentLength;
		private Node leftChild;
		private Node rightChild;
		private int level;// level==0 表示

		public Node(int left, int right) {
			this.LeftRange = left;
			this.RightRange = right;
			this.Mid = ((this.RightRange - this.LeftRange) >> 1) + this.LeftRange;
		}

		private Node leftNode() {
			if (this.leftChild == null) {
				this.leftChild = new Node(this.LeftRange, this.Mid);
			}
			return this.leftChild;
		}

		private Node rightNode() {
			if (this.rightChild == null) {
				this.rightChild = new Node(this.Mid, this.RightRange);
			}
			return this.rightChild;
		}

		public void update(int left, int right, int update, int[] compressX) {
			if (left >= right) {// 必须有宽度，不能包含等于
				return;
			}
			if (left == this.LeftRange && right == this.RightRange) {
				level += update;
				if (level == 1) {
					this.segmentLength = compressX[right] - compressX[left];
				} else if (level == 0) {// bug1 ，这个地方赋值为0
					// 这个地方一层没有，不一定是0啊，错这里了。只是[LeftRange,RightRange]连续的长度没了，但是不代表没有组合的长度
					this.segmentLength = this.leftNode().segmentLength + this.rightNode().segmentLength;
				}
			} else {
				this.leftNode().update(left, Math.min(this.Mid, right), update, compressX);
				this.rightNode().update(Math.max(this.Mid, left), right, update, compressX);
				if (level == 0) {// 就丢了这一句话，这块不能无脑左右加的，因为父节点可能比子节点大，无脑加反而变小了
					// 因为没有从父节点下发任务的过程 ， bug2 这个地方无脑给了和，不一定是和啊
					this.segmentLength = this.leftNode().segmentLength + this.rightNode().segmentLength;
				}

			}

		}
	}

	// [0,0,2,2],[1,0,2,3],[1,0,3,1]
	// [x,y,x,y]
	// 1.压缩横向坐标
	// 2.建立纵向线段
	// 3.从下向上，向线段树中添加线段，一层加完同上一层的层高差结算面积。
	// 每一层可能来自这一层的矩形下边，增加当前层长度，也可能来自之前矩形的上边，减少当前层长度。
	@Override
	public int rectangleArea(int[][] rectangles) {
		int MOD = (int) 1e9 + 7;
		int Len = rectangles.length;
		int ADD = 1; // 线段数据结构，延长线段，延长的长度取决于横向坐标差
		int SUB = -1; // 线段数据结构，缩短线段
		int[][] segment = new int[Len << 1][4];// 横向线段数据结构：[线段高度,左端横坐标,右端横坐标,增/减]
		int segmentIndex = 0; // 线段数据结构，线段树索引
		TreeSet<Integer> unique = new TreeSet<>((a, b) -> a - b);// 为压缩横向坐标数据，去掉重复的横坐标 && 从小到大排序
		for (int i = 0; i < Len; i++) {// 完成横向压缩和纵向建立线段
			int[] cur = rectangles[i];
			unique.add(cur[0]);// 横向压缩
			unique.add(cur[2]);// 横向压缩
			segment[segmentIndex++] = new int[] { cur[1], cur[0], cur[2], ADD };// 纵向扫描
			segment[segmentIndex++] = new int[] { cur[3], cur[0], cur[2], SUB };// 纵向扫描
		}
		Arrays.sort(segment, (a, b) -> a[0] == b[0] ? b[3] - a[3] : a[0] - b[0]);// 从下到上依次排序
		Map<Integer, Integer> mapx = new HashMap<>();// 建立原坐标与压缩坐标索引
		int[] compressX = new int[unique.size()];// 压缩坐标找原x坐标
		int range = 0;// 压缩坐标范围 && 编号
		for (Integer num : unique) {
			compressX[range] = num;
			mapx.put(num, range++);
		}
		long ans = 0;
		long lastY = 0;
		Node root = new Node(0, range - 1);
		int i = 0;
		while (i < segmentIndex) {
			int[] cur = segment[i];
			long curY = cur[0];// [线段高度,左端横坐标,右端横坐标,增/减]
			if (curY == lastY) {
				root.update(mapx.get(cur[1]), mapx.get(cur[2]), cur[3], compressX);
				i++;
			} else {
				long area = (curY - lastY) * root.segmentLength;
//				ans += area % MOD;
				ans = (ans + area) % MOD;
				lastY = curY;
			}
		}
		return (int) ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug6();
		so.debug5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

	private void forSegmentTree(int[][] rectangles) {
		// [0,0,2,2],[1,0,2,3],[1,0,3,1]
		// [x,y,x,y],描绘线段，压缩横坐标，描绘平行于x轴的横向线段
		int Len = rectangles.length;
		int ADD = 1;
		int SUB = -1;
		int[][] segment = new int[Len << 1][4];// 横向线段数据结构：[线段高度,左端横坐标,右端横坐标,增/减]
		int segmentIndex = 0;
		for (int i = 0; i < Len; i++) {
			int[] cur = rectangles[i];
			segment[segmentIndex++] = new int[] { cur[1], cur[0], cur[2], ADD };
			segment[segmentIndex++] = new int[] { cur[3], cur[0], cur[2], SUB };
		}
		Arrays.sort(segment, (a, b) -> a[0] - b[0]);
		HelpDebug.print(segment);
	}

	private void compressX(int[][] rectangles) {
		int Len = rectangles.length;
		TreeSet<Integer> unique = new TreeSet<>((a, b) -> a - b);// 为压缩横向坐标数据，去掉重复的横坐标
		for (int i = 0; i < Len; i++) {
			int[] cur = rectangles[i];
			unique.add(cur[0]);
			unique.add(cur[2]);
		}
		Map<Integer, Integer> mapx = new HashMap<>();// 建立原坐标与压缩坐标索引
		int range = 1;// 压缩坐标范围
		for (Integer num : unique) {
			mapx.put(num, range++);
		}
	}

}
